import java.util.Arrays;
import java.util.Scanner;

public class Subsequence {
    /**
     * 动态规划解答最长公共子序列问题
     * @param args
     */
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.println("请输入字符串S1：");
        String s1=in.nextLine();
        System.out.println("请输入字符串S2：");
        String s2 = in.nextLine();

//        int a=longestCommonSubsequence(s1,s2);
//        System.out.println("最长公共子序列长度为："+a);
        longestCommonSubsequence(s1,s2);

    }

    public static void longestCommonSubsequence(String text1,String text2){
        // 利用动态规划进行解答
        char[] char1=text1.toCharArray();
        char[] char2=text2.toCharArray();
        int [][]dp=new int[char1.length+1][char2.length+1];
        for(int i=1;i<= char1.length;i++){
            char c1=char1[i-1];
            for(int j=1;j<= char2.length;j++){
                char c2=char2[j-1];
                if(c1==c2){
                    // 此时需要列出状态方程
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        System.out.println("最长子序列的长度为： "+ dp[char1.length][char2.length]);

        // 打印出公共子序列

        int m= char1.length,n=char2.length;
        int lmax=dp[m][n];
//        StringBuilder res=new StringBuilder();
        char[]res=new char[lmax];
        while(m>0 && n>0){
            if(char1[m-1]==char2[n-1]){
//                res.append(char1[m-1]);
                res[lmax-1]=char1[m-1];
                m--;
                n--;
                lmax--;
            }else if(dp[m-1][n]>dp[m][n-1]){
                m--;
            }else {
                n--;
            }
        }
        System.out.println("最长子序列为："+ Arrays.toString(res));
//        System.out.println("最长子序列为："+res.reverse());
//        dp[char1.length][char2.length];

    }
}
